#ifndef MSORT_HPP
#define MSORT_HPP
#include <vector>
namespace myh{
    constexpr size_t THRESHOLD=16;
    template <typename RandomIt>
    void sort(RandomIt begin,RandomIt end) {
        using ValueType=typename std::iterator_traits<RandomIt>::value_type;
        const size_t n=end-begin;
        size_t curr_size,left_start;
        if(n<=THRESHOLD) {
            for(auto i=begin+1;i<end;++i) {
                ValueType key=*i;
                auto j=i;
                while(j>begin&&*(j-1)>key) *j=*(j-1),--j;
                *j=key;
            }
            return;
        }
        for(curr_size=1;curr_size<n;curr_size*=2) {
            for(left_start=0;left_start<n;left_start+=2*curr_size) {
                const size_t mid=left_start+curr_size-1;
                const size_t right_end=std::min(left_start+2*curr_size-1,n-1);
                if(mid<right_end) {
                    auto left_it=begin+left_start;
                    auto mid_it=begin+mid,right_it=begin+right_end;
                    std::vector<ValueType> left_arr(left_it,mid_it+1);
                    std::vector<ValueType> right_arr(mid_it+1,right_it+1);
                    auto left_idx=left_arr.begin(),right_idx=right_arr.begin();
                    auto k=left_it;
                    while(left_idx!=left_arr.end()&&right_idx!=right_arr.end()) {
                        if(*left_idx<=*right_idx) *k++=*left_idx++;
                        else *k++=*right_idx++;
                    }
                    while(left_idx!=left_arr.end()) *k++=*left_idx++;
                    while(right_idx!=right_arr.end()) *k++=*right_idx++;
                }
            }
        }
    }
}
#endif